package com.syg;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 树
 *
 * 需要将节点抽象成一个类吗？树跟节点是有共性的,树是由很多节点组成的
 */
public class Tree {

    //存储所有节点的集合
    private List<TreeNode> listNode;


    /**
     *
     * @param args
     */
    public static void main(String[] args) {
        Integer[] integers = new Integer[]{1,2,3,4,5,6,7,8};
        LinkedList<Integer> inList = new LinkedList<>(Arrays.asList(integers));

        Tree tree = new Tree();
        tree.createBinaryTree(inList);

        // 先序遍历
        tree.preOrderTraverse(tree.getRoot());
    }

    /**
     * 创建满二叉树或完全二叉树
     */
    public void createBinaryTree(LinkedList<Integer> inList) {
        // 0,校验
        if (null == inList || inList.isEmpty()) {
            return;
        }
        // 1,将传进来的数组转换成节点并存入list中
        listNode = new LinkedList<>();
        for (Integer item : inList) {
            listNode.add(new TreeNode(item));
        }

        // 2,构造父子之间的关系  1   2  3      4  5  6  7  8  9
        for(int parentIndex = 0; parentIndex < inList.size()/2-1; parentIndex++){
            listNode.get(parentIndex).leftChild = listNode.get(parentIndex*2+1);//添加左儿子
            listNode.get(parentIndex).rightChild = listNode.get(parentIndex*2+2);//添加右儿子
        }

        //对于最后一个节点,单独处理
        int lastIndex = inList.size()/2-1;
        // 此时有左孩子
        listNode.get(lastIndex).leftChild = listNode.get(lastIndex*2+1);

        // 如果数组个数为奇数，这时最后一个节点有右儿子
        if(inList.size() % 2 != 0){
            listNode.get(lastIndex).rightChild = listNode.get(lastIndex*2+2);
        }
    }

    // 先序遍历 根-左-右
    public void preOrderTraverse(TreeNode root){
        if(root == null){
            return;
        }

        System.out.print(root.data+" ");
        preOrderTraverse(root.leftChild);
        preOrderTraverse(root.rightChild);
    }

    // 中序遍历 左-根-右
    public void inOrderTraverse(TreeNode root){
        if(root == null){
            return;
        }

        inOrderTraverse(root.leftChild);
        System.out.print(root.data+" ");
        inOrderTraverse(root.rightChild);
    }

    // 后序遍历 左-右-根
    public void postOrderTraverse(TreeNode root){
        if(root == null){
            return;
        }

        postOrderTraverse(root.leftChild);
        postOrderTraverse(root.rightChild);
        System.out.print(root.data+" ");
    }


    /**
     * 获取根节点
     * @return
     */
    public TreeNode getRoot(){
        // 空树判断
        if (listNode == null || listNode.isEmpty()) {
            throw new RuntimeException("please create tree");
        }

        // 非空,获取第一个节点(因为我们在插入的时候,用第一个作为了根节点)
        return listNode.get(0);
    }

    //宽度优先遍历/广度优先遍历
    //创建一个队列，先把根节点存到队列中，然后当队列不是空的时候，将队列头删除并输出其值，如果其儿子节点存在，那么就将其儿子节点存到队列中，直到队列是空的
    public void BFS(TreeNode root){
        if(root == null){
            return;
        }

        //创建队列，存储节点
        Queue<TreeNode> queue = new LinkedList<TreeNode>();

        //把根节点存到队尾
        queue.offer(root);

        //当队列不是空的，删除队列头节点，将其儿子节点存到队列中
        while(!queue.isEmpty()){
            TreeNode head = queue.poll();
            System.out.print(head.data+" ");

            if(head.leftChild != null){
                queue.offer(head.leftChild);
            }
            if(head.rightChild != null){
                queue.offer(head.rightChild);
            }
        }

        System.out.println();
    }

    //宽度优先遍历
    //创建一个栈，先把根节点存到栈中，当栈不是空的时候，将栈顶元素弹出，如果其儿子节点存在，就把其儿子节点存到栈中，直到栈是空的
    public void DFS(TreeNode root){
        if(root == null){
            return;
        }

        //创建栈，存储节点
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();

        //把根节点压到栈底
        stack.push(root);

        //当栈不是空的时候，弹出栈顶元素，并将其儿子节点压到栈中
        while(!stack.isEmpty()){
            TreeNode head = stack.pop();
            System.out.print(head.data+" ");

            if(head.leftChild != null){
                stack.push(head.leftChild);
            }
            if(head.rightChild != null){
                stack.push(head.rightChild);
            }
        }

        System.out.println();
    }

    /**
     * 由于二叉树由节点构成,所有节点是其内部类
     *
     * 结论：(便于理解面向对象思想)如果类A中包含类B，就可以直接将B定义在A中，方便使用
     */
    private class TreeNode {
        /**
         * 左节点
         */
        TreeNode leftChild;
        /**
         * 右节点
         */
        TreeNode rightChild;
        /**
         * 节点值
         */
        Integer data;

        public TreeNode(Integer data) {
            this.data = data;
        }
    }
}
